package com.faiz.algorithm;

public class MinimumDeleteSum {
    public int minimumDeleteSum(String s1, String s2) {
        // 思路：找到两个字符串中的最大公共子序列
        int m = s1.length();
        int n = s2.length();

        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();

        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (c1[i - 1] == c2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(c1[i - 1] + dp[i - 1][j], c2[j - 1] + dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        String s1 = "sea";
        String s2 = "eat";
        MinimumDeleteSum minimumDeleteSum = new MinimumDeleteSum();
        int sum = minimumDeleteSum.minimumDeleteSum(s1, s2);
        System.out.println(sum);
    }
}
